The present invention relates to the creation of computer-generated images both in the form of still pictures and video imagery, and, in particular, relates to efficient process, apparatus, and systems for creating an image made up by compositing multiple components. The invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for creating an image made up by compositing multiple components.
Computer generated images are typically made up of many differing components, graphical elements or graphical objects which are rendered and composited together to create a final image. In recent times, an xe2x80x9copacity channelxe2x80x9d (also known as a xe2x80x9cmattexe2x80x9d, an xe2x80x9calpha channelxe2x80x9d, or simply xe2x80x9copacityxe2x80x9d) has been commonly used. The opacity channel contains information regarding the transparent nature of each element. The opacity channel is stored alongside each instance of a colour, so that, for example, a pixel-based image with opacity, stores an opacity value as part of the representation of each pixel. An element without explicit opacity channel information is typically understood to be fully opaque or partially transparent within some defined bounds of the element, and assumed to be completely transparent outside those bounds.
An expression tree offers a systematic means for representing an image in terms of its constituent elements and which facilitates later rendering. Expression trees typically comprise a plurality of nodes including leaf nodes, unary nodes and binary, nodes. Nodes of higher degree, or of alternative definition may also be used. A leaf node, being the outer most node of an expression tree, has no descendent nodes and represents a primitive constituent of an image. Unary nodes represent an operation which modifies the pixel data coming out of the part of the tree below the unary operator. Unary nodes include such operations as colour conversions, convolutions (blurring etc) and operations such as red-eye removal. A binary node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. Binary nodes represent an operation which combines the pixel data of its too children to form a single result. For example, a binary node may be one of the standard xe2x80x9ccompositing operatorsxe2x80x9d such as OVER, IN, OUT, ATOP and alpha-XOR, examples of which and others are shown in FIG. 2.
Several of the above types of nodes can be combined to form a compositing tree. An example of this is shown in FIG. 1. The result of the left-hand side of the compositing tree may be interpreted as a colour converted image being clipped to spline boundaries. This construct is composited with a second image.
Although the non-transparent area of a graphical element can of itself be of certain size, it need not be entirely visible in a final image, or only a portion of the element may have an effect on the final image. For example, assume an image of a certain size is to be displayed on a display. If the image is positioned so that only the top left corner of the image is displayed by the display device, the remainder of the image is not displayed. The final image as displayed on the display device thus comprises the visible portion of the image, and the invisible portion in such a case need not be rendered.
Another way in which only a portion of an element may have an effect is when the portion is obscured by another element. For example, a final image to be displayed (or rendered) may comprise one or more opaque graphical elements, some of which obscure other graphical elements. Hence, the obscured elements have no effect on the final image.
A conventional graphics rendering model considers each node to be conceptually infinite in extent. Therefore, to construct the final image, a conventional system would apply a compositing equation at every pixel of the output image. Interactive frame rates of the order greater than 15 frames per second can be achieved by relatively brute-force approaches in these conventional systems, because the actual pixel operations are quite simple and can be highly optimised. This highly optimised code is fast enough to produce acceptable frame rates without requiring complex code. However, this is certainly not true in an alpha compositing environment where complex expressions can be very computationally expensive. Thus, the per-pixel cost of compositing can be quite high since typically an image is rendered in 24-bit colour in addition to an 8-bit alpha channel, thus giving 32 bits per pixel. Each compositing operator has to deal with each of the four channels. Therefore, the approach of completely generating every pixel of every required frame when needed is inefficient. This problem is particularly relevant when performing xe2x80x9cDynamic Renderingxe2x80x9d.
Dynamic rendering refers to the generation of multiple successive images. Given a compositing tree, it is possible to generate region groups (containing regions) for the compositing tree. The compositing tree represents an initial image. Changes to the tree can be made to make the tree represent a new image. The region groups and the region description of the tree are updated to reflect the modified tree. Performance can be improved by exploiting commonality between the two images.
Australian Patent Publication No. AU-A-47329/99 discloses a method of creating a series of images formed by rendering graphical objects. The method disclosed by Australian Patent Publication No. AU-A-47329/99 exploits the opaqueness of the graphical objects to be rendered during a compositing operation. The contents of Australian Patent Publication No. AU-A47329/99 are incorporated herein by cross-reference.
An example implementation of the method disclosed by AU-A-47329/99 utilises a label referred to as a xe2x80x9cContents Label (CL)xe2x80x9d which represents a unique symbolic expression describing the method of construction of image data. The contents label disclosed by AU-A- 47329/99 is implemented as an index into an array of contents label property structures, which are represented by the tag CL_Properties. The terms in the symbolic expression are used to distinguish between different categorisations of the source of image data. Region groups of two distinct leaf nodes in a compositing tree can contain regions that are labelled with distinct contents labels even if their actual image data is equivalent. A region of the image is substantially defined by the boundary outlines of two or more overlapping graphical elements. The example implementation disclosed by AU-A-47329/99 utilises a system of unique integers to represent contents labels. For example, xe2x80x9c23xe2x80x9d represents xe2x80x9c(A over B) over Cxe2x80x9d.
AU-A-47329/99 also described the concepts of xe2x80x9cprimaryxe2x80x9d and xe2x80x9csecondaryxe2x80x9d damage in order to demonstrate that it is not always necessary to regenerate an entire image as a result of a change to the compositing tree representing the image. Any region of the image including a compositing equation with an object that has been altered in some way can be said to suffer primary damage. Secondary damage is said to have been incurred by a region, if the object upon which the boundary outline of the region (but not content) depends, changes in some way. By keeping track of dependencies between regions of different content, it only becomes necessary to regenerate image data in regions whose contents have become damaged. These dependencies are referred to as xe2x80x9cprimaryxe2x80x9d and xe2x80x9csecondaryxe2x80x9d dependencies. A primary dependency is a contents label (e.g. Lxe2x80x2) representing an expression which has been constructed by combining L and sonic other contents label. A secondary dependency is a contents label Lxe2x80x3 which can be indirectly affected if the image represented by the contents label L has changed in some way that the boundary of L is affected, For example, FIG. 9 shows the region subdivision and the respective compositing expressions for a simple compositing tree. Consider therefore the situation in which object A moves by a small amount relative to the other objects. Some regions in the region group at the root of the tree will be affected by A moving.
If opaque case optimisations are ignored, the regions with compositing expressions which include A will be significantly affected by A moving. The region numbers which are so affected are 2, 3, 5 and 6. When updating the region group at the root of the tree, those regions will need their region descriptions and proxies completely recalculated. This situation is an example of primary damage. Further, regions that abut regions which have A in their compositing expression are also effected by A moving, though not as severely as those regions with primary damage. In the example, these other affected regions are 1, 4, 7 and 8. When updating the region group at the root of the tree, these regions will need their region descriptions recalculated. However, their proxies will only need to be recalculated in areas of the new region which were not included in the corresponding earlier region. This situation is an example of secondary damage as discussed above.
The example implementation disclosed by AU-A-47329/99 was deficient in the method used to manage the determination of secondary dependencies and hence secondary damage. Given the existence of a particular composite contents label, the example implementation disclosed by AU-A-47329/99 generated every possible related contents label which could possibly be secondary damaged if the region and associated contents label in question became primary damaged. In compositions with high xe2x80x9cdepth complexityxe2x80x9d a large number of contents labels were generated, the vast majority of which did not exist. Depth complexity in this context means the number of leaf-node graphical objects which intersect one another. Performance degraded rapidly as depth complexity increased, due to the significant burden of creating and damaging such a large number of contents labels.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.
According to one aspect of the present invention there is provided a method of creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure representing a compositing expression, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said method comprising the steps of:
(a) for each said node:
(i)dividing a component image space in which said outlines are defined into at least one mutually exclusive region, each said region being related to at least one graphical object;
(ii)examining each said region to determine those objects that contribute to the region;
(b) creating dependency information identifying those said regions that will be affected by a change in any one of said regions;
(c) rendering a first image of said series by compositing all regions substantially according to said hierarchical structure;
(d) in response to at least one change to at least one of said nodes:
(i)examining said dependency information to identify those of said regions affected by said at least one change, wherein at least one of said regions is indirectly affected by a change to at least one other of said regions, said indirectly affected region being identified by inference through association with at least one other of said affected regions;
(ii)for each node with affected regions, updating the corresponding identified regions and incorporating into said node those (any) new regions arising from the change and/or removing any of said regions that are no longer relevant,
(iii)updating said dependency information to reflect changes to said hierarchical structure;
(iv)rendering a further image of said series by compositing (only) those regions affected by said at least one change; and
(e) repeating step (d) for further changes to at least one of said nodes.
According to another aspect of the present invention there is provided a method of creating a series of images, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said method comprising the steps of:
(a) for each said node:
(iii)dividing a space in which said outlines are defined into at least one mutually exclusive region;
(iv)examining each said region to determine those objects that contribute to the region;
(b) creating dependency information based on said examination,
(c) rendering a first image of said series utilising said hierarchical structure; and then, in response to at least one chance to at least one of said nodes;
(d) examining said dependency information;
(i)for a node with affected regions, updating the corresponding regions, wherein at least one of said regions is indirectly affected by a change to at least one other of said regions, said indirectly affected region being identified by inference through association with at least one other of said affected regions;
(ii) updating said dependency information;
(iii)rendering a further image of said series by compositing those regions affected by said at least one change; and
(e) repeating step (d) for further changes to at least one of said nodes.
According to still another aspect of the present invention there is provided a method of creating a series of images, said images being formed by rendering at least a plurality of graphical objects to be composited according to a hierarchical structure, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, said method comprising the steps of:
(a) for each said node:
(i)dividing a component image space in which said graphical objects are defined into at least one region;
(ii) examining each said region;
(b) creating dependency information for each of said regions;
(c) rendering a first image of said series utilising said hierarchical structure; and then, in response to at least one change to at least one of said nodes;
(d) examining said dependency information;
(i)for a node with affected regions, updating the corresponding information, wherein at least one of said regions is indirectly affected by a change to at least one other of said regions, said indirectly affected region being identified by inference from being associated with at least one other of said affected regions;
(ii) updating said dependency record;
(iii)rendering a further image of said series; and
(e) repeating step (d) for further changes to at least one of said nodes.
According to still another aspect of the present invention there is provided a apparatus for creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure representing a compositing expression, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said apparatus comprising:
division means for dividing a component image space in which said outlines are defined into at least one mutually exclusive region, each said region being related to at least one graphical object and each said region being examined to determine those objects that contribute to the region;
dependency information creation means for creating dependency information to identify those said regions that will be affected by a change in any one of said regions;
render means for rendering a first image of said series by compositing all regions substantially according to said hierarchical structure;
examination means for examining said dependency information in response to at least one change to at least one of said nodes, to identify those of said regions affected by said at least one change, wherein at least one of said regions is indirectly affected by a change to at least one other of said regions, said indirectly affected region being identified by inference through association with at least one other of said affected regions, and wherein for each node with affected regions, the corresponding identified regions are updated by an updating means and those (any) new regions arising from the change are incorporated into said node and/or any of said regions that are no longer relevant are removed, said dependency information is updated to reflect changes to said hierarchical structure, and wherein said render means renders a further image of said series by compositing (only) those regions affected by said at least one change
According to still another aspect of the present invention there is provided a computer readable medium for storing a program for apparatus which processes data, said processing comprising a process for creating a series of images, each member of said series being related to a preceding member, said images being formed by rendering a plurality of graphical objects to be composited according to a hierarchical structure representing a compositing expression, said hierarchical structure including a plurality of nodes each representing a component of at least one of said images, each of said objects having a predetermined outline, said program comprising:
code for dividing a component image space in which said outlines are defined into at least one mutually exclusive region, each said region being related to at least one graphical object;
code for examining each said region to determine those objects that contribute to the region;
code for creating dependency information identifying those said regions that will be affected by a change in any one of said regions;
code for rendering a first image of said series by compositing all regions substantially according to said hierarchical structure;
code for examining said dependency information in response to at least one change to at least one of said nodes, to identify those of said regions affected by said at least one change, wherein at least one of said regions is indirectly affected by a change to at least one other of said regions, said indirectly affected region being identified by inference through association with at least one other of said affected regions;
code for updating the corresponding identified regions for each node with affected regions, and incorporating into said node those (any) new regions arising from the change and/or removing any of said regions that are no longer relevant;
code for updating said dependency information to reflect changes to said hierarchical structure; and
code for rendering a further image of said series by compositing (only) those regions affected by said at least one change.